package com.practice.niuke.new_direct_basics.class15;

/**
 * 排成一条线的纸牌博弈问题
 * 【题目】
 * 给定一个整型数组 arr， 代表数值不同的纸牌排成一条线。 玩家 A 和玩家 B 依次拿走每张纸 牌，
 * 规定玩家 A 先拿， 玩家 B 后拿， 但是每个玩家每次只能拿走最左或最右的纸牌， 玩家 A 和 玩
 * 家 B 都绝顶聪明。 请返回最后获胜者的分数。
 * 【举例】
 * arr=[1,2,100,4]。
 * 开始时， 玩家 A 只能拿走 1 或 4。 如果玩家 A 拿走 1， 则排列变为[2,100,4]， 接下来玩家 B
 * 可以拿走 2 或 4， 然后继续轮到玩家 A。 如果开始时玩家 A 拿走 4， 则排列变为[1,2,100]， 接
 * 下 来玩家 B 可以拿走 1 或 100， 然后继续轮到玩家 A。 玩家 A 作为绝顶聪明的人不会先拿 4，
 * 因为 拿 4 之后， 玩家 B 将拿走 100。 所以玩家 A 会先拿 1， 让排列变为[2,100,4]， 接下来玩
 * 家 B 不管 怎么选， 100 都会被玩家 A 拿走。 玩家 A 会获胜， 分数为 101。 所以返回 101。
 * arr=[1,100,2]。
 * 开始时， 玩家 A 不管拿 1 还是 2， 玩家 B 作为绝顶聪明的人， 都会把 100 拿走。 玩家 B 会
 * 获胜， 分数为 100。 所以返回 100。
 */
public class Code03_CardsInLine {

    /**
     * （1）暴力递归法主流程函数(TODO：标记调用暴力递归的主函数)
     *
     * @param arr 数组
     * @return int
     */
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(
                f(arr, 0, arr.length - 1),
                s(arr, 0, arr.length - 1)
        );
    }


    /**
     * （1）暴力递归：
     * 先手函数
     * 当前该你拿，arr[L..R]
     * 返回你的最好分数
     *
     * @param arr 数组
     * @param L   左边界
     * @param R   右边界
     * @return int
     */
    public static int f(int[] arr, int L, int R) {
        if (L == R) {
            // L==R说明只剩下一张牌了
            return arr[L];
        }
        // 先手在[L..R]范围上拿牌，最优策略下的得分（先手会确保自己拿到尽可能大的值）
        return Math.max(
                // 拿arr[L], 后手在[L+1...R]范围上拿牌
                arr[L] + s(arr, L + 1, R),
                // 拿arr[R], 后手在[L...R-1]范围上拿牌
                arr[R] + s(arr, L, R - 1)
        );
    }

    /**
     * （1）暴力递归：
     * 后手函数(当前是先手挑选情况下的后手函数)
     * 当前不该你拿，是对方在arr[i..j]范围上拿
     * 返回你的最好分数
     *
     * @param arr 数组
     * @param L   左边界
     * @param R   右边界
     * @return int
     */
    public static int s(int[] arr, int L, int R) {
        if (L == R) {
            // L==R说明只剩下一张牌了,先手肯定会直接拿走。
            return 0;
        }
        // 后手在[L..R]范围上拿牌，最优策略下的得分（“先手”会确保“后手”拿到尽可能小的值）
        return Math.min(
                // “先手”拿了arr[L]，此时轮到“后手”在[L+1...R]范围上先手拿牌
                f(arr, L + 1, R),
                // “先手”拿了arr[R]，此时轮到“后手”在[L...R-1]范围上先手拿牌
                f(arr, L, R - 1)
        );
    }

    /**
     * (2)由“暴力递归法”推导出“动态规划法”(TODO：暴力递归改成动态规划)
     *
     * @param arr 数组
     * @return int
     */
    public static int windp(int[] arr) {
        // 无效参数
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        // 先手函数二维表，此时每个元素初始化为0，对角线元素f[i][i]要在下面初始化为arr[i]。
        int[][] f = new int[N][N];
        // 后手函数二维表，此时每个元素初始化为0,对角线元素不用再初始化。
        int[][] s = new int[N][N];
        // 将先手函数二维表对角线元素初始化为1
        for (int i = 0; i < N; i++) {
            f[i][i] = arr[i];
        }
        // [0][0]位置向右下方移动求解当前斜线上的值
        // [0][1]位置向右下方移动求解当前斜线上的值
        // [0][2]位置向右下方移动求解当前斜线上的值
        // ...
        // [0][N-1]位置向右下方移动求解当前斜线上的值
        for (int col = 1; col < N; col++) {
            // 对角线的出发位置是[0][col]
            int L = 0;
            int R = col;
            while (L < N && R < N) {
                f[L][R] = Math.max(
                        // 拿arr[L], 后手在[L+1...R]范围上拿牌
                        arr[L] + s[L + 1][R],
                        // 拿arr[R], 后手在[L...R-1]范围上拿牌
                        arr[R] + s[L][R - 1]);
                s[L][R] = Math.min(
                        // “先手”拿了arr[L]，此时轮到“后手”在[L+1...R]范围上先手拿牌
                        f[L + 1][R],
                        // “先手”拿了arr[R]，此时轮到“后手”在[L...R-1]范围上先手拿牌
                        f[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(f[0][N - 1], s[0][N - 1]);
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
        System.out.println(windp(arr));
        System.out.println(win1(arr));
    }

}
